﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
namespace RH
{
    class Program
    {

        public static LinkBinaryTree<int> btree = new LinkBinaryTree<int>(0); // 用来计算递归深度的
        static StreamWriter  deepsw = new StreamWriter(".\\deepsw.txt", false, Encoding.GetEncoding("gb2312")); // 保存递归深度
        static StreamWriter hsw = new StreamWriter(".\\hsw.txt", false, Encoding.GetEncoding("gb2312")); // 保存所有马尔科夫状态H
        static void Main(string[] args)
        {
            //Console.WriteLine(R(13,4));

            GenWholeH(15, 20);

            Console.ReadLine();
        }


        /// <summary>
        /// 给出某个H的H-
        /// </summary>
        /// <param name="H">H值</param>
        /// <param name="_k">_k是最高位1到最低比特所占的位数</param>
        /// <returns></returns>
        static UInt32 R(UInt32 H, int _k)
        {
            int k = _k - 1;
            UInt32 H_minus = 0;
            for (;;)
            {
                //H_minus = H % ((UInt32)Math.Pow(2, k));
                H_minus = H % ((UInt32)(1 << k));
                if (H_minus == 0 || H_minus == H)
                {
                    return H_minus;
                }
                H = H_minus;
                k--;
            }
        }



        /// <summary>
        /// Generate j 1s in k bits, 产生所有k个bit中包含j个1的数值 (第一种递归方法形成)
        /// </summary>
        /// <param name="n"></param>
        /// <param name="m"></param>
        /// <param name="result"></param>
        /// <param name="len"></param>
        static void GenMOnesInNbits1(int k, int j, int[] index, int len)
        {
            if (j == 0)
            {
                for (int i = 0; i < len; i++)
                    Console.Write( $"{index[len - 1 - i]} ");
                Console.WriteLine();
                return;
            }
            for (int i = k; i >= j; i--)
            {
                index[j - 1] = i;
                GenMOnesInNbits1(i - 1, j - 1, index, len);
            }
        }

        /// <summary>
        /// Generate j 1s in k bits, 产生所有k个bit中包含j个1的数值 (第二种递归方法形成)
        /// </summary>
        /// <param name="k">k bits</param>
        /// <param name="j">j ones</param>
        /// <param name="index">buffer to save the one's index</param>
        /// <param name="len">buffer length<param>
        /// <param name="set">set used to save value<param>
        /// <param name="tnode">与算法无关，仅用于计算递归深度<param>
        /// <param name="leftOrRight">与算法无关，仅用于计算递归深度<param>
        static void GenMOnesInNbits(int k, int j, int[] index, int len, List<UInt32> set,  TreeNode<int> tnode = null, int leftOrRight = 0)
        {
            // 下面这部分用来计算递归深度
            TreeNode<int> tnodeleft=null, tnoderight=null;

            switch (leftOrRight)
            {
                case 0:
                    if (tnode != null)
                    {
                        tnodeleft = btree.InsertL(0, tnode);
                        tnoderight = btree.InsertR(0, tnode);
                    }
                    break;
                case 1:
                    tnodeleft = tnoderight = btree.InsertL(0, tnode);
                    break;
                case 2:
                    tnodeleft = tnoderight = btree.InsertR(0, tnode);
                    break;
            }
            // 开始算法过程
            if (j == 0 || k < j)
            {
                if (j == 0)
                {
                    UInt32 H = 0;
                    for (int i = 0; i < len; i++)
                    {
                        H += (UInt32)(1 << index[i]);
                        Console.Write($"{index[len - 1 - i]} ");
                    }
                    set.Add(H);
                    Console.Write($"value: {H}");
                    Console.WriteLine();
                }
                return ;
            }
            index[j - 1] = k - 1;
            GenMOnesInNbits(k - 1, j - 1, index, len,set, tnodeleft, 1);
            GenMOnesInNbits(k - 1, j, index, len,set, tnoderight, 2);
            
        }

        /// <summary>
        /// 形成m/n滑动窗最小马尔科夫状态集合。 注意不包含0和A(*)。
        /// </summary>
        /// <param name="m"></param>
        /// <param name="n"></param>
        /// <returns></returns>
        static List<UInt32> GenWholeH(int m, int n)
        {
            
            List<UInt32> set = new List<uint>();
            for (int j = 1; j <= m - 1; j++)
            {
                int[] index = new int[j];
                int k = n - m + j;
                GenMOnesInNbits(k, j, index, j, set, btree.Head);

                deepsw.WriteLine($"k:{k} bis,j:{j} ones， recure: {btree.MaxDeepLevel} ");// 保存最大递归深度
                btree = new LinkBinaryTree<int>(0); // 重新进行递归
            }
            deepsw.Close();
            set.Sort();
            // 下面将最小马尔科夫状态空间写入文件
            int cnt = 0; // H的计数个数
            foreach (var H in set)
            {
                hsw.Write(H.ToString() + ",");
                cnt++;
                if (cnt >= 30)
                {
                    hsw.WriteLine(); // 写一个换行符
                    cnt = 0;
                }
            }
            hsw.Close();
            return set;
        }
    }
}
